home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1994 / MacHack 1994.toast / MacHack™94 / Miscellaneous / Randy Thelen / ThreadedSort / Sort ƒ / QuickSort.cp next >
Encoding:
Text File  |  1994-06-26  |  4.1 KB  |  180 lines  |  [TEXT/MMCC]
  1. /*----------------------------------------------------------------------------
  2.  
  3.     QuickSort.cp
  4.  
  5.     fastQSort() is a replacement for qsort().  Compared with the Think C library
  6.     version of qsort, fastQSort is about 3 times faster (it takes 1/3 the time), 
  7.     and its speed isn't dependent on the data being sorted.
  8.     
  9.     One problem with qsort is that when the data is not in random order -- for
  10.     example when it's already ordered, in reverse order, or almost sorted -- then 
  11.     qsort exhibits worst case behavior of N*N/2 operations.  For N=1024 this can 
  12.     take about 30 seconds, instead of the usual 0.8 seconds.  The fastQSort 
  13.     algorithm doesn't have this problem, because it randomly selects the pivot
  14.     element, and so for N=1024 it requires about 0.26 secs +/- 0.02 secs.
  15.     
  16.     Also, because fastQSort doesn't exhibit worst case behavior, it doesn't 
  17.     require as much stack space, even though it has 12 bytes more of local
  18.     variables.
  19.     
  20.     The things that make fastQSort so much faster than qsort are:
  21.     
  22.     1)    fastQSort picks the pivot element randomly, so it doesn't display worst
  23.         case behavior.
  24.         
  25.     2)    fastQSort uses pointers and pointer arithmetic, avoiding multiplication
  26.         whenever possible.
  27.     
  28.     3)    qsort uses std_swap() to swap the data between two locations, and 
  29.         std_swap loops through the data 3 times to perform the exchange!  In
  30.         comparison, swapMem() loops through the data just once.
  31.         
  32.     4)    fastQSort uses register variables whenever it makes good sense to do so.
  33.     
  34.     
  35.     Researched and written by:
  36.     
  37.         Haydn Huntley
  38.         Haydn's Consulting
  39.         203 West Stone
  40.         Fairfield, Iowa  52556
  41.         (515) 472-7025
  42.         
  43.     During the school year, I may be reached at the following address:
  44.     
  45.         Haydn Huntley
  46.         Eigenmann Hall #289
  47.         Indiana University
  48.         Bloomington, IN  47406
  49.         (812) 857-8620
  50.         
  51.     E-mail:  huntley@copper.ucs.indiana.edu
  52.  
  53.     This version was modified by Randy Thelen of Apple Computer, Inc.
  54.     This version works within the shell of SortPicts.
  55.     
  56.     Hopefully, we'll see faster Sorts with QuickSort than with Heap sorts and the like
  57. ----------------------------------------------------------------------------*/
  58.  
  59. #include "SortPicts.h"
  60.  
  61. /*
  62.  *    QSort is a non C++ routine which is called thrugh a ProcPtr (essentially)
  63.  *    It will call the real SortPicts::QSort
  64.  */
  65. void    QSort( SortPicts *sortPicts)
  66. {
  67.     sortPicts->QSort();
  68. }
  69.  
  70.  
  71. /*
  72.  *    QSort
  73.  *    -----
  74.  *
  75.  *    THis routine merely calls QuickSortEngine with the whole range of Data.
  76.  *    I've always wondered about the 0 to N instead of 0 to N-1; but the program
  77.  *    works and I don't really care to investigate.
  78.  */
  79. void    SortPicts::QSort( void)
  80. {
  81.         QuickSortEngine( 0, N);
  82. }
  83.  
  84.  
  85. /*
  86.  *    ChooseMedian
  87.  *    ------------
  88.  *
  89.  *    This is the crux of Quick Sort.  This is why it's fast.
  90.  */
  91. void    SortPicts::ChooseMedian( long a, long b, long c)
  92. {
  93.     long        m;        //    median
  94.  
  95.     if( sortData[a] > sortData[b])
  96.         if( sortData[a] > sortData[c])
  97.             if( sortData[b] > sortData[c])
  98.                 m = b;
  99.             else
  100.                 m = c;
  101.         else
  102.             m = a;
  103.     else
  104.         if( sortData[a] > sortData[c])
  105.             m = a;
  106.         else
  107.             if( sortData[b] > sortData[c])
  108.                 m = c;
  109.             else
  110.                 m = b;
  111.     
  112.     if( a != m)
  113.         ExchangeSortItem( a, m);
  114. }
  115.  
  116.  
  117.  
  118. /*
  119.  *    QuickSortEngine
  120.  *    ---------------
  121.  *
  122.  *    This routine is the divide and conquor engine.  It's no big deal. 
  123.  */
  124. void    SortPicts::QuickSortEngine( long left, long right)
  125. {
  126.     long            n;
  127.     long            i, j;
  128.     
  129.     while( (n = right - left) > 1)
  130.     {
  131.         if( n < kPivotCutoff)        //    Use a random pivot
  132.             ExchangeSortItem( left + Random( n), left);
  133.         else
  134.             ChooseMedian( left, left + (n >> 1), 
  135.                           left + Random( n));
  136.         
  137.         i = left;
  138.         j = right;
  139.         
  140.         while( 1)
  141.         {
  142.             i++;
  143.             while( (i < right) && (sortData[i] < sortData[left]))
  144.                 i++;
  145.             
  146.             j--;
  147.             while( (j > left) && (sortData[j] > sortData[left]))
  148.                 j--;
  149.             
  150.             if( i >= j)
  151.                 break;
  152.             
  153.             ExchangeSortItem( i, j);
  154.         }
  155.         
  156.         if( j == left)
  157.         {
  158.             left++;
  159.             continue;
  160.         }
  161.         
  162.         ExchangeSortItem( left, j);
  163.         if( (j - left) < (right - (j + 1)))
  164.         {
  165.             /* equivalent to doFastQSort (j + qSize, last);        */
  166.             /* to save stack space                                */
  167.             QuickSortEngine( left, j);
  168.             left = j + 1;
  169.         }
  170.         else
  171.         {
  172.             /* equivalent to doFastQSort (first, j);            */
  173.             /* to save stack space                                */
  174.             QuickSortEngine( j+1, right);
  175.             right = j;
  176.         }
  177.     }
  178. }
  179.  
  180.